package com.zfcer.chapter01;

import org.junit.Test;

/**
 * @Classname Fiboracci 斐波拉契数列 【斐波拉契数列公式：F(n) = F(n-1) + F(n-2), 其中F(0) = F(1) = 1】
 * @Description 完成对斐波拉契数列的递归、非递归实现
 * @Created by zfcer
 * @Date 2022/4/16 10:46
 */
public class Fiboracci {

    /**
     * 非递归实现1：尝试分析其时间和空间复杂度
     * @param n
     * @return F(n)
     */
    public long getFact1(int n){
        long startTime = System.currentTimeMillis();
        // 初始化
        long[] f = new long[n+1];
        f[0] = f[1] = 1;
        // 注意代码的健壮性
        for(int i=2; i<=n; i++){
            f[i] = f[i-1] + f[i-2];
        }
        long useTime = System.currentTimeMillis() - startTime;
        System.out.println("getFact1消耗时间：" + useTime);
        return f[n];
    }

    /**
     * 非递归实现2：尝试分析其时间和空间复杂度
     * @param n
     * @return F(n)
     */
    public long getFact2(long n){
        long startTime = System.currentTimeMillis();
        long f0 = 1, f1 = 1;
        long fn = f1;
        // 注意代码的健壮性
        for(long i=2; i<=n; i++){
            fn = f0 + f1;
            f0 = f1;
            f1 = fn;
        }
        long useTime = System.currentTimeMillis() - startTime;
        System.out.println("getFact2消耗时间：" + useTime);
        return fn;
    }


    /**
     * 递归实现3：尝试分析其时间和空间复杂度
     * @param n
     * @return F(n)
     */
    public long getFact3(long n){
        if(n <= 1) return 1;
        // 递归的过程使用到了递归栈
        return getFact3(n-1) + getFact3(n-2);
    }

    /**
     * 测试用例
     */
    @Test
    public void test(){
        //System.out.println("getFact1(10) = " + getFact1(50));
        //System.out.println("getFact2(10) = " + getFact2(50));
        //System.out.println("getFact3(10) = " + getFact3(50));


        getFact1(100000000);
        getFact2(100000000);

        long startTime = System.currentTimeMillis();
        getFact3(45);
        long useTime = System.currentTimeMillis() - startTime;
        System.out.println("getFact3消耗时间：" + useTime);

    }
}
